/*
 * @lc app=leetcode.cn id=207 lang=cpp
 * @lcpr version=30204
 *
 * [207] 课程表
 */


// @lcpr-template-start
using namespace std;
#include <algorithm>
#include <array>
#include <bitset>
#include <climits>
#include <deque>
#include <functional>
#include <iostream>
#include <list>
#include <queue>
#include <stack>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
// @lcpr-template-end
// @lc code=start
class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        // 构建图和入度数组
        vector<vector<int>> graph(numCourses);
        vector<int> inDegree(numCourses, 0);

        // 构建邻接表和计算入度
        for (const auto& pre : prerequisites) {
            graph[pre[1]].push_back(pre[0]);
            inDegree[pre[0]]++;
        }

        // 将所有入度为0的节点加入队列
        queue<int> q;
        for (int i = 0; i < numCourses; ++i) {
            if (inDegree[i] == 0) {
                q.push(i);
            }
        }

        // 拓扑排序
        int count = 0; // 记录已处理的节点数
        while (!q.empty()) {
            int course = q.front();
            q.pop();
            count++;

            // 遍历当前节点的邻接节点
            for (int next : graph[course]) {
                inDegree[next]--;
                if (inDegree[next] == 0) {
                    q.push(next);
                }
            }
        }

        // 如果处理的节点数等于课程总数，说明可以完成所有课程
        return count == numCourses;
    }
/*
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        // 构建图
        vector<vector<int>> graph(numCourses);
        for (const auto& pre : prerequisites) {
            graph[pre[1]].push_back(pre[0]);
        }

        // 状态数组：0=未访问，1=正在访问，2=已访问
        vector<int> visited(numCourses, 0);

        // 检测环的DFS函数
        function<bool(int)> hasCycle = [&](int course) {
            if (visited[course] == 1) return true;  // 当前节点正在访问，说明存在环
            if (visited[course] == 2) return false; // 当前节点已访问完成，无需重复检查

            visited[course] = 1; // 标记为正在访问
            for (int next : graph[course]) {
                if (hasCycle(next)) return true; // 如果发现环，直接返回
            }
            visited[course] = 2; // 标记为已访问完成
            return false;
        };

        // 遍历每个节点，检测是否存在环
        for (int i = 0; i < numCourses; ++i) {
            if (hasCycle(i)) return false; // 如果存在环，无法完成课程
        }

        return true; // 如果没有环，可以完成所有课程
    }
*/
};
// @lc code=end



/*
// @lcpr case=start
// 2\n[[1,0]]\n
// @lcpr case=end

// @lcpr case=start
// 2\n[[1,0],[0,1]]\n
// @lcpr case=end

 */

